// Copyright [2022] <Tianyu Zhu, Shizhen Zhao, Zihang Ren>

#ifndef PULSE_PLUS_H_
#define PULSE_PLUS_H_

#include <functional>
#include <queue>
#include <map>
#include <vector>

#include "algorithm.h"
#include "graph.h"

class PulsePlus : public Algorithm {
 public:
    PulsePlus() {}
    ~PulsePlus();
    void SetupTopology(Graph* graph) override;
    Path FindPath(const Flow& flow) override;
    void print() const;

 private:
    struct Node {
        Node(NodeId id_in, int distance_in, NodeId pre_id_in = -1,
             int link_delay_in = 0)
            : id(id_in), distance(distance_in), pre_id(pre_id_in),
              link_delay(link_delay_in) {}

        friend bool operator<(const Node &a, const Node &b) {
            return a.distance > b.distance;
        }
        NodeId id;
        int distance;
        NodeId pre_id;
        int link_delay;  // link delay from Node pre_id to Node id.
    };

    struct PulseInfo {
        PulseInfo() {}
        void Clear() {
            delay_to_cost_map.clear();
        }
        std::map<int, int> delay_to_cost_map;
    };

    // Helper functions
    void CostBasedDijkstra(NodeId dst_node);
    void DelayBasedDijkstra(NodeId dst_node);
    void Dfs(NodeId u, Path& path);
    bool check(NodeId u, int cost, int delay);
    bool update(NodeId u, const Path& path, double p);

    // Variables for initialization
    int* cost_map_;
    Path* min_cost_path_map_;
    int* delay_map_;
    int num_nodes_;

    // Variables for pulse search
    bool* visited_;
    PulseInfo* info_;
    Flow flow_;
    int total_cost_;
    std::vector<Path> results_;
};

#endif  // PULSE_PLUS_H_